import java.util.Deque;
import java.util.LinkedList;

/**
 * @ClassName Offer_09
 * @Description 双栈模拟队列
 * @Author clockTown
 * @Date 2021/8/12 15:29
 * @Version 1.0
 */
class Offer09 {
}

/**
 * 版本 v0
 * 栈1用来模拟队列，栈底-队首，栈顶-队尾，添加数据到队尾-添加数据到栈顶；
 * 栈2用来翻转栈内元素，每次要删除队首元素的时候，就将栈1的元素依次弹出到栈2，直到栈1为空，然后弹出栈2的栈顶元素（该元素就是所求队首元素）
 * 弹出队首元素后再将栈2内的元素依次弹回栈1中
 */
class CQueueV0 {

    private Deque<Integer> stack1;
    private Deque<Integer> stack2;

    public CQueueV0() {
        this.stack1 = new LinkedList<>();
        this.stack2 = new LinkedList<>();
    }

    public void appendTail(int value) {
        stack1.push(value);
    }

    public int deleteHead() {
        if (!stack1.isEmpty()){
            while (!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            Integer pop = stack2.pop();
            while (!stack2.isEmpty()){
                stack1.push(stack2.pop());
            }
            return pop;

        }
        return -1;
    }
}

/**
 * 版本 v1
 * 栈1用来模拟队列，栈底-队首，栈顶-队尾，添加数据到队尾-添加数据到栈顶；
 * 栈2用来维护需要弹出的队首元素，每次要删除队首元素的时候，检查栈2是否有元素，如果有就弹出，如果没有
 * 就将栈1的元素依次弹出到栈2，直到栈1为空，然后弹出栈2的栈顶元素（如果存在的话，该元素就是所求队首元素），
 * 如果最后栈2为空，返回-1
 */
class CQueueV1 {

    private Deque<Integer> inStack;
    private Deque<Integer> outStack;

    public CQueueV1() {
        this.inStack = new LinkedList<>();
        this.outStack = new LinkedList<>();
    }

    public void appendTail(int value) {
        inStack.push(value);
    }

    public int deleteHead() {

        if(outStack.isEmpty()){
            if (!inStack.isEmpty()){
                while (!inStack.isEmpty()){
                    outStack.push(inStack.pop());
                }

            }
        }
        return outStack.isEmpty() ? -1 : outStack.pop();
    }
}

